using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0099. 恢复二叉搜索树")]
    public class No0099_RecoverTree : AbsBaseTestItem
    {
        /*
        二叉搜索树中的两个节点被错误地交换。
        请在不改变其结构的情况下，恢复这棵树。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }
        public override void OnTest()
        {
            bool EqualsFun(TreeNode r1, TreeNode r2) => r1.ToJSONString() == r2.ToJSONString();
            TreeNode Calc(TreeNode root)
            {
                RecoverTree(root);
                return root;
            }
            Assert.TestExe(Calc,
                new TreeNode(1)
                {
                    left = new TreeNode(3)
                    {
                        right = new TreeNode(2),
                    }
                },
                equalsMethod: EqualsFun,
                new TreeNode(3)
                {
                    left = new TreeNode(1)
                    {
                        right = new TreeNode(2),
                    }
                });
            Assert.TestExe(Calc,
                new TreeNode(3)
                {
                    left = new TreeNode(1),
                    right = new TreeNode(4)
                    {
                        left = new TreeNode(2)
                    }
                },
                equalsMethod: EqualsFun,
                new TreeNode(2)
                {
                    left = new TreeNode(1),
                    right = new TreeNode(4)
                    {
                        left = new TreeNode(3)
                    }
                });
        }

        public void RecoverTree(TreeNode root)
        {
            TreeNode x = null, y = null, pred = null, predecessor = null;

            while (root != null)
            {
                if (root.left != null)
                {
                    // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                    predecessor = root.left;
                    while (predecessor.right != null && predecessor.right != root)
                    {
                        predecessor = predecessor.right;
                    }

                    // 让 predecessor 的右指针指向 root，继续遍历左子树
                    if (predecessor.right == null)
                    {
                        predecessor.right = root;
                        root = root.left;
                    }
                    // 说明左子树已经访问完了，我们需要断开链接
                    else
                    {
                        if (pred != null && root.val < pred.val)
                        {
                            y = root;
                            if (x == null)
                            {
                                x = pred;
                            }
                        }
                        pred = root;

                        predecessor.right = null;
                        root = root.right;
                    }
                }
                // 如果没有左孩子，则直接访问右孩子
                else
                {
                    if (pred != null && root.val < pred.val)
                    {
                        y = root;
                        if (x == null)
                        {
                            x = pred;
                        }
                    }
                    pred = root;
                    root = root.right;
                }
            }
            void swap(TreeNode x, TreeNode y)
            {
                int tmp = x.val;
                x.val = y.val;
                y.val = tmp;
            }
            swap(x, y);
        }
    }
}
